Adding some more judges, here and there.

[and.git] / lib / Mi manual de algoritmos / version_maraton_nacional_2008 / src / geometria / is_inside_concave_polygon.tex

% Generator: GNU source-highlight, by Lorenzo Bettini, http://www.gnu.org/software/src-highlite

{\ttfamily \raggedright {
\noindent
\mbox{}\textit{\textcolor{Brown}{/*********}} \\
\mbox{}\textit{\textcolor{Brown}{\ *\ Point\ *}} \\
\mbox{}\textit{\textcolor{Brown}{\ *********}} \\
\mbox{}\textit{\textcolor{Brown}{\ *\ A\ simple\ point\ class\ used\ by\ some\ of\ the\ routines\ below.}} \\
\mbox{}\textit{\textcolor{Brown}{\ *\ Anything\ else\ that\ supports\ .x\ and\ .y\ will\ work\ just\ as}} \\
\mbox{}\textit{\textcolor{Brown}{\ *\ well.\ There\ are\ 2\ variants\ -\ double\ and\ int.}} \\
\mbox{}\textit{\textcolor{Brown}{\ **/}} \\
\mbox{}\textbf{\textcolor{Blue}{struct}}\ P\ \textcolor{Red}{\{}\ \textcolor{ForestGreen}{double}\ x\textcolor{BrickRed}{,}\ y\textcolor{BrickRed}{;}\ \textbf{\textcolor{Black}{P}}\textcolor{BrickRed}{()}\ \textcolor{Red}{\{\}}\textcolor{BrickRed}{;}\ \textbf{\textcolor{Black}{P}}\textcolor{BrickRed}{(}\ \textcolor{ForestGreen}{double}\ q\textcolor{BrickRed}{,}\ \textcolor{ForestGreen}{double}\ w\ \textcolor{BrickRed}{)}\ \textcolor{BrickRed}{:}\ \textbf{\textcolor{Black}{x}}\textcolor{BrickRed}{(}\ q\ \textcolor{BrickRed}{),}\ \textbf{\textcolor{Black}{y}}\textcolor{BrickRed}{(}\ w\ \textcolor{BrickRed}{)}\ \textcolor{Red}{\{\}}\ \textcolor{Red}{\}}\textcolor{BrickRed}{;} \\
\mbox{}\textbf{\textcolor{Blue}{struct}}\ P\ \textcolor{Red}{\{}\ \textcolor{ForestGreen}{int}\ x\textcolor{BrickRed}{,}\ y\textcolor{BrickRed}{;}\ \textbf{\textcolor{Black}{P}}\textcolor{BrickRed}{()}\ \textcolor{Red}{\{\}}\textcolor{BrickRed}{;}\ \textbf{\textcolor{Black}{P}}\textcolor{BrickRed}{(}\ \textcolor{ForestGreen}{int}\ q\textcolor{BrickRed}{,}\ \textcolor{ForestGreen}{int}\ w\ \textcolor{BrickRed}{)}\ \textcolor{BrickRed}{:}\ \textbf{\textcolor{Black}{x}}\textcolor{BrickRed}{(}\ q\ \textcolor{BrickRed}{),}\ \textbf{\textcolor{Black}{y}}\textcolor{BrickRed}{(}\ w\ \textcolor{BrickRed}{)}\ \textcolor{Red}{\{\}}\ \textcolor{Red}{\}}\textcolor{BrickRed}{;} \\
\mbox{} \\
\mbox{}\textit{\textcolor{Brown}{/***************}} \\
\mbox{}\textit{\textcolor{Brown}{\ *\ Polar\ angle\ *}} \\
\mbox{}\textit{\textcolor{Brown}{\ ***************}} \\
\mbox{}\textit{\textcolor{Brown}{\ *\ Returns\ an\ angle\ in\ the\ range\ [0,\ 2*Pi)\ of\ a\ given\ Cartesian\ point.}} \\
\mbox{}\textit{\textcolor{Brown}{\ *\ If\ the\ point\ is\ (0,0),\ -1.0\ is\ returned.}} \\
\mbox{}\textit{\textcolor{Brown}{\ *\ REQUIRES:}} \\
\mbox{}\textit{\textcolor{Brown}{\ *\ include\ math.h}} \\
\mbox{}\textit{\textcolor{Brown}{\ *\ define\ EPS\ 0.000000001,\ or\ your\ choice}} \\
\mbox{}\textit{\textcolor{Brown}{\ *\ P\ has\ members\ x\ and\ y.}} \\
\mbox{}\textit{\textcolor{Brown}{\ **/}} \\
\mbox{}\textcolor{ForestGreen}{double}\ \textbf{\textcolor{Black}{polarAngle}}\textcolor{BrickRed}{(}\ P\ p\ \textcolor{BrickRed}{)} \\
\mbox{}\textcolor{Red}{\{} \\
\mbox{}\ \ \ \ \textbf{\textcolor{Blue}{if}}\textcolor{BrickRed}{(}\ \textbf{\textcolor{Black}{fabs}}\textcolor{BrickRed}{(}\ p\textcolor{BrickRed}{.}x\ \textcolor{BrickRed}{)}\ \textcolor{BrickRed}{$<$=}\ EPS\ \textcolor{BrickRed}{\&\&}\ \textbf{\textcolor{Black}{fabs}}\textcolor{BrickRed}{(}\ p\textcolor{BrickRed}{.}y\ \textcolor{BrickRed}{)}\ \textcolor{BrickRed}{$<$=}\ EPS\ \textcolor{BrickRed}{)}\ \textbf{\textcolor{Blue}{return}}\ \textcolor{BrickRed}{-}\textcolor{Purple}{1.0}\textcolor{BrickRed}{;} \\
\mbox{}\ \ \ \ \textbf{\textcolor{Blue}{if}}\textcolor{BrickRed}{(}\ \textbf{\textcolor{Black}{fabs}}\textcolor{BrickRed}{(}\ p\textcolor{BrickRed}{.}x\ \textcolor{BrickRed}{)}\ \textcolor{BrickRed}{$<$=}\ EPS\ \textcolor{BrickRed}{)}\ \textbf{\textcolor{Blue}{return}}\ \textcolor{BrickRed}{(}\ p\textcolor{BrickRed}{.}y\ \textcolor{BrickRed}{$>$}\ EPS\ \textcolor{BrickRed}{?}\ \textcolor{Purple}{1.0}\ \textcolor{BrickRed}{:}\ \textcolor{Purple}{3.0}\ \textcolor{BrickRed}{)}\ \textcolor{BrickRed}{*}\ \textbf{\textcolor{Black}{acos}}\textcolor{BrickRed}{(}\ \textcolor{Purple}{0}\ \textcolor{BrickRed}{);} \\
\mbox{}\ \ \ \ \textcolor{ForestGreen}{double}\ theta\ \textcolor{BrickRed}{=}\ \textbf{\textcolor{Black}{atan}}\textcolor{BrickRed}{(}\ \textcolor{Purple}{1.0}\ \textcolor{BrickRed}{*}\ p\textcolor{BrickRed}{.}y\ \textcolor{BrickRed}{/}\ p\textcolor{BrickRed}{.}x\ \textcolor{BrickRed}{);} \\
\mbox{}\ \ \ \ \textbf{\textcolor{Blue}{if}}\textcolor{BrickRed}{(}\ p\textcolor{BrickRed}{.}x\ \textcolor{BrickRed}{$>$}\ EPS\ \textcolor{BrickRed}{)}\ \textbf{\textcolor{Blue}{return}}\textcolor{BrickRed}{(}\ p\textcolor{BrickRed}{.}y\ \textcolor{BrickRed}{$>$=}\ \textcolor{BrickRed}{-}EPS\ \textcolor{BrickRed}{?}\ theta\ \textcolor{BrickRed}{:}\ \textcolor{BrickRed}{(}\ \textcolor{Purple}{4}\ \textcolor{BrickRed}{*}\ \textbf{\textcolor{Black}{acos}}\textcolor{BrickRed}{(}\ \textcolor{Purple}{0}\ \textcolor{BrickRed}{)}\ \textcolor{BrickRed}{+}\ theta\ \textcolor{BrickRed}{)}\ \textcolor{BrickRed}{);} \\
\mbox{}\ \ \ \ \textbf{\textcolor{Blue}{return}}\textcolor{BrickRed}{(}\ \textcolor{Purple}{2}\ \textcolor{BrickRed}{*}\ \textbf{\textcolor{Black}{acos}}\textcolor{BrickRed}{(}\ \textcolor{Purple}{0}\ \textcolor{BrickRed}{)}\ \textcolor{BrickRed}{+}\ theta\ \textcolor{BrickRed}{);} \\
\mbox{}\textcolor{Red}{\}} \\
\mbox{} \\
\mbox{}\textit{\textcolor{Brown}{/************************}} \\
\mbox{}\textit{\textcolor{Brown}{\ *\ Point\ inside\ polygon\ *}} \\
\mbox{}\textit{\textcolor{Brown}{\ ************************}} \\
\mbox{}\textit{\textcolor{Brown}{\ *\ Returns\ true\ iff\ p\ is\ inside\ poly.}} \\
\mbox{}\textit{\textcolor{Brown}{\ *\ PRE:\ The\ vertices\ of\ poly\ are\ ordered\ (either\ clockwise\ or}} \\
\mbox{}\textit{\textcolor{Brown}{\ *\ \ \ \ \ \ counter-clockwise.}} \\
\mbox{}\textit{\textcolor{Brown}{\ *\ POST:\ Modify\ code\ inside\ to\ handle\ the\ special\ case\ of\ "{}on\ an\ edge"{}.}} \\
\mbox{}\textit{\textcolor{Brown}{\ *\ REQUIRES:}} \\
\mbox{}\textit{\textcolor{Brown}{\ *\ polarAngle()}} \\
\mbox{}\textit{\textcolor{Brown}{\ *\ include\ math.h}} \\
\mbox{}\textit{\textcolor{Brown}{\ *\ include\ vector}} \\
\mbox{}\textit{\textcolor{Brown}{\ *\ define\ EPS\ 0.000000001,\ or\ your\ choice}} \\
\mbox{}\textit{\textcolor{Brown}{\ **/}} \\
\mbox{}\textcolor{ForestGreen}{bool}\ \textbf{\textcolor{Black}{pointInPoly}}\textcolor{BrickRed}{(}\ P\ p\textcolor{BrickRed}{,}\ vector\textcolor{BrickRed}{$<$}\ P\ \textcolor{BrickRed}{$>$}\ \textcolor{BrickRed}{\&}poly\ \textcolor{BrickRed}{)} \\
\mbox{}\textcolor{Red}{\{} \\
\mbox{}\ \ \ \ \textcolor{ForestGreen}{int}\ n\ \textcolor{BrickRed}{=}\ poly\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{size}}\textcolor{BrickRed}{();} \\
\mbox{}\ \ \ \ \textcolor{ForestGreen}{double}\ ang\ \textcolor{BrickRed}{=}\ \textcolor{Purple}{0.0}\textcolor{BrickRed}{;} \\
\mbox{}\ \ \ \ \textbf{\textcolor{Blue}{for}}\textcolor{BrickRed}{(}\ \textcolor{ForestGreen}{int}\ i\ \textcolor{BrickRed}{=}\ n\ \textcolor{BrickRed}{-}\ \textcolor{Purple}{1}\textcolor{BrickRed}{,}\ j\ \textcolor{BrickRed}{=}\ \textcolor{Purple}{0}\textcolor{BrickRed}{;}\ j\ \textcolor{BrickRed}{$<$}\ n\textcolor{BrickRed}{;}\ i\ \textcolor{BrickRed}{=}\ j\textcolor{BrickRed}{++}\ \textcolor{BrickRed}{)} \\
\mbox{}\ \ \ \ \textcolor{Red}{\{} \\
\mbox{}\ \ \ \ \ \ \ \ P\ \textbf{\textcolor{Black}{v}}\textcolor{BrickRed}{(}\ poly\textcolor{BrickRed}{[}i\textcolor{BrickRed}{].}x\ \textcolor{BrickRed}{-}\ p\textcolor{BrickRed}{.}x\textcolor{BrickRed}{,}\ poly\textcolor{BrickRed}{[}i\textcolor{BrickRed}{].}y\ \textcolor{BrickRed}{-}\ p\textcolor{BrickRed}{.}y\ \textcolor{BrickRed}{);} \\
\mbox{}\ \ \ \ \ \ \ \ P\ \textbf{\textcolor{Black}{w}}\textcolor{BrickRed}{(}\ poly\textcolor{BrickRed}{[}j\textcolor{BrickRed}{].}x\ \textcolor{BrickRed}{-}\ p\textcolor{BrickRed}{.}x\textcolor{BrickRed}{,}\ poly\textcolor{BrickRed}{[}j\textcolor{BrickRed}{].}y\ \textcolor{BrickRed}{-}\ p\textcolor{BrickRed}{.}y\ \textcolor{BrickRed}{);} \\
\mbox{}\ \ \ \ \ \ \ \ \textcolor{ForestGreen}{double}\ va\ \textcolor{BrickRed}{=}\ \textbf{\textcolor{Black}{polarAngle}}\textcolor{BrickRed}{(}\ v\ \textcolor{BrickRed}{);} \\
\mbox{}\ \ \ \ \ \ \ \ \textcolor{ForestGreen}{double}\ wa\ \textcolor{BrickRed}{=}\ \textbf{\textcolor{Black}{polarAngle}}\textcolor{BrickRed}{(}\ w\ \textcolor{BrickRed}{);} \\
\mbox{}\ \ \ \ \ \ \ \ \textcolor{ForestGreen}{double}\ xx\ \textcolor{BrickRed}{=}\ wa\ \textcolor{BrickRed}{-}\ va\textcolor{BrickRed}{;} \\
\mbox{}\ \ \ \ \ \ \ \ \textbf{\textcolor{Blue}{if}}\textcolor{BrickRed}{(}\ va\ \textcolor{BrickRed}{$<$}\ \textcolor{BrickRed}{-}\textcolor{Purple}{0.5}\ \textcolor{BrickRed}{$|$$|$}\ wa\ \textcolor{BrickRed}{$<$}\ \textcolor{BrickRed}{-}\textcolor{Purple}{0.5}\ \textcolor{BrickRed}{$|$$|$}\ \textbf{\textcolor{Black}{fabs}}\textcolor{BrickRed}{(}\ \textbf{\textcolor{Black}{fabs}}\textcolor{BrickRed}{(}\ xx\ \textcolor{BrickRed}{)}\ \textcolor{BrickRed}{-}\ \textcolor{Purple}{2}\ \textcolor{BrickRed}{*}\ \textbf{\textcolor{Black}{acos}}\textcolor{BrickRed}{(}\ \textcolor{Purple}{0}\ \textcolor{BrickRed}{)}\ \textcolor{BrickRed}{)}\ \textcolor{BrickRed}{$<$}\ EPS\ \textcolor{BrickRed}{)} \\
\mbox{}\ \ \ \ \ \ \ \ \textcolor{Red}{\{} \\
\mbox{}\ \ \ \ \ \ \ \ \ \ \ \ \textit{\textcolor{Brown}{//\ POINT\ IS\ ON\ THE\ EDGE}} \\
\mbox{}\ \ \ \ \ \ \ \ \ \ \ \ \textbf{\textcolor{Black}{assert}}\textcolor{BrickRed}{(}\ \textbf{\textcolor{Blue}{false}}\ \textcolor{BrickRed}{);} \\
\mbox{}\ \ \ \ \ \ \ \ \ \ \ \ ang\ \textcolor{BrickRed}{+=}\ \textcolor{Purple}{2}\ \textcolor{BrickRed}{*}\ \textbf{\textcolor{Black}{acos}}\textcolor{BrickRed}{(}\ \textcolor{Purple}{0}\ \textcolor{BrickRed}{);} \\
\mbox{}\ \ \ \ \ \ \ \ \ \ \ \ \textbf{\textcolor{Blue}{continue}}\textcolor{BrickRed}{;} \\
\mbox{}\ \ \ \ \ \ \ \ \textcolor{Red}{\}} \\
\mbox{}\ \ \ \ \ \ \ \ \textbf{\textcolor{Blue}{if}}\textcolor{BrickRed}{(}\ xx\ \textcolor{BrickRed}{$<$}\ \textcolor{BrickRed}{-}\textcolor{Purple}{2}\ \textcolor{BrickRed}{*}\ \textbf{\textcolor{Black}{acos}}\textcolor{BrickRed}{(}\ \textcolor{Purple}{0}\ \textcolor{BrickRed}{)}\ \textcolor{BrickRed}{)}\ ang\ \textcolor{BrickRed}{+=}\ xx\ \textcolor{BrickRed}{+}\ \textcolor{Purple}{4}\ \textcolor{BrickRed}{*}\ \textbf{\textcolor{Black}{acos}}\textcolor{BrickRed}{(}\ \textcolor{Purple}{0}\ \textcolor{BrickRed}{);} \\
\mbox{}\ \ \ \ \ \ \ \ \textbf{\textcolor{Blue}{else}}\ \textbf{\textcolor{Blue}{if}}\textcolor{BrickRed}{(}\ xx\ \textcolor{BrickRed}{$>$}\ \textcolor{Purple}{2}\ \textcolor{BrickRed}{*}\ \textbf{\textcolor{Black}{acos}}\textcolor{BrickRed}{(}\ \textcolor{Purple}{0}\ \textcolor{BrickRed}{)}\ \textcolor{BrickRed}{)}\ ang\ \textcolor{BrickRed}{+=}\ xx\ \textcolor{BrickRed}{-}\ \textcolor{Purple}{4}\ \textcolor{BrickRed}{*}\ \textbf{\textcolor{Black}{acos}}\textcolor{BrickRed}{(}\ \textcolor{Purple}{0}\ \textcolor{BrickRed}{);} \\
\mbox{}\ \ \ \ \ \ \ \ \textbf{\textcolor{Blue}{else}}\ ang\ \textcolor{BrickRed}{+=}\ xx\textcolor{BrickRed}{;} \\
\mbox{}\ \ \ \ \textcolor{Red}{\}} \\
\mbox{}\ \ \ \ \textbf{\textcolor{Blue}{return}}\textcolor{BrickRed}{(}\ ang\ \textcolor{BrickRed}{*}\ ang\ \textcolor{BrickRed}{$>$}\ \textcolor{Purple}{1.0}\ \textcolor{BrickRed}{);} \\
\mbox{}\textcolor{Red}{\}} \\

} \normalfont\normalsize